//封装双向链表
function DoublyLinkedList() {
  // 属性
  this.head = null;
  this.tail = null;
  this.length = 0;

  //   内部节点类
  function Node(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }

  //   方法封装
  //   1.append方法(后面追加)
  DoublyLinkedList.prototype.append = function (data) {
    //1，根据data创建节点
    let newNode = new Node(data);
    //2，判断添加的是否是第一个节点
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    // 最后长度＋1
    this.length += 1;
  };

  //2，将链表转成字符串形式
  //2.1.toString方法
  DoublyLinkedList.prototype.toString = function () {
    return this.backwardString();
  };

  //2.2.forwardString方法 (从后往前遍历数据)
  DoublyLinkedList.prototype.forwardString = function () {
    //1，定义变量
    let current = this.tail;
    let resultString = "";
    //2，依次向前遍历，获取每一个节点
    while (current) {
      resultString += current.data + " ";
      current = current.prev;
    }
    return resultString;
  };

  //2.3.backwardString方法 (从第一个向后遍历数据)
  DoublyLinkedList.prototype.backwardString = function () {
    //1，定义变量
    let current = this.head;
    let resultString = "";
    //2.依次向后遍历，获取每一个节点
    while (current) {
      resultString += current.data + " ";
      current = current.next;
    }
    return resultString;
  };

  //3.insert方法
  DoublyLinkedList.prototype.insert = function (position, data) {
    // 1.越界判断
    if (position < 0 || position > this.length) return false;
    //2，根据data创建新的节点
    let newNode = new Node(data);
    //3，判断原来的列表是否为空
    if (this.length == 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 判断 position 插入的位置是否为0
      if (position == 0) {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      } else if (position == this.length) {
        // 最后的节点
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
      } else {
        // 往中间插入
        let current = this.head;
        let index = 0;
        while (index++ < position) {
          //找到正确的节点
          current = current.next;
          newNode.prev = current.prev;
          current.prev.next = newNode;
          current.prev = newNode;
        }
      }
    }
    // 最后length +1
    this.length += 1;
    return true;
  };

  //4.get方法
  DoublyLinkedList.prototype.get = function (position) {
    //1.  越界判断
    if (position < 0 || position >= this.length) return null;
    // 2.获取元素位置
    let current = this.head;
    let index = 0;
    // 判断获取元素的位置
    if (position < this.length / 2) {
      while (index++ < position) {
        current = current.next;
      }
    } else {
      current = this.tail;
      index = this.length - 1;
      while (index-- > position) {
        current = current.prev;
      }
    }

    return current.data;
  };

  //5.indexOf方法
  DoublyLinkedList.prototype.indexOf = function (data) {
    //1，定义变量
    let current = this.head;
    let index = 0;
    //2，查找和data相同的节点
    while (current) {
      if (current.data == data) {
        return index;
      }
      current = current.next;
      index++;
    }
    // 没有找到 返回-1
    return -1;
  };

  //6.update方法
  DoublyLinkedList.prototype.update = function (position, newData) {
    // 1.越界判断
    if (position < 0 || position >= this.length) return false;

    //2，寻找正确的节点
    let current = this.head;
    let index = 0;
    while (index++ < position) {
      current = current.next;
    }
    //3，修改找到节点的data信息
    current.data = newData;
    return true;
  };

  // 7.removeAt方法
  DoublyLinkedList.prototype.removeAt = function (position) {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null;

    let current = this.head; //主要是为了返回被删除的节点

    //2，判断是否只有一个节点
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      //判断是否删除的是第一个节点
      if (position == 0) {
        this.head.next.prev = null;
        this.head = this.head.next;
      } else if (position == this.length - 1) {
        current = this.tail;
        //删除最后的节点
        this.tail.prev.next = null;
        this.tail = this.tail.prev;
      } else {
        // 其他情况
        let index = 0;

        while (index++ < position) {
          current = current.next;
        }
        // 找到了相关的节点
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
    }
    // 最后 len-1
    this.length--;

    return current.data;
  };

  // 8.remove方法
  DoublyLinkedList.prototype.remove = function (data) {
    //1，根据data获取下标值
    let index = this.indexOf(data);
    // 删除对应位置的节点
    return this.removeAt(index);
  };

  //9.isEmpty方法
  DoublyLinkedList.prototype.isEmpty = function () {
    return this.length == 0;
  };

  //10.size方法
  DoublyLinkedList.prototype.size = function () {
    return this.length;
  };

  // 11.获取链表的第一个元素
  DoublyLinkedList.prototype.getFirst = function () {
    return this.head.data;
  };
  // 12.获取链表最后一个元素
  DoublyLinkedList.prototype.getLast = function () {
    return this.tail.data;
  };
}

// 测试代码
let list = new DoublyLinkedList();
// append方法
list.append("AA");
list.append("BB");
list.append("CC");
list.append("DD");
list.insert(0, "EE");
list.update(1, "修改AA");
console.log(list.update(10, "修改AA"));
console.log(list.get(10));
console.log(list);
console.log(list.get(0));
console.log(list.get(1));
console.log("反着获取链表元素", list.get(4));
console.log("反着获取链表元素", list.get(3));

console.log(list.indexOf("CC"));

console.log("我删除了 ", list.removeAt(1));
console.log("我使用remove删除了 ", list.remove("DD"));

console.log("我获取最后一个元素", list.getLast());

console.log("正向", list.toString());
console.log("反向", list.forwardString());
